#include <vector>

using namespace std;

// 单词接龙
// 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
// 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk ：
// 每一对相邻的单词只差一个字母。
// 对于 1 <= i <= k 时，每个 si 都在 wordList 中
// 注意， beginWord 不需要在 wordList 中。sk == endWord
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList
// 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目
// 如果不存在这样的转换序列，返回 0 。
// 测试链接 : https://leetcode.cn/problems/word-ladder/

// 双向广搜的做法
class Solution 
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        // 将 vector 转成哈希表，用于开始判断某个词是否在词典中
        unordered_set<string> dict(wordList.begin(), wordList.end());
        // 词典中不包含 endWord，直接返回 0，表示不存在转换序列
        if(!dict.count(endWord)) return 0;

        // smallLevel：数量小的一侧
        // bigLevel：数量大的一侧
        // nextLevel：由数量小的一侧，所扩展出的下一层列表
        unordered_set<string> smallLevel, bigLevel, nextLevel;
        smallLevel.insert(beginWord);
        bigLevel.insert(endWord);
        for(int len = 2; !smallLevel.empty(); ++len)
        {
            // 从小侧扩展
            for(auto& str : smallLevel)
            {
                string tmp = str;
                // 尝试去替换 tmp 中的每一个字符
                for(int i = 0; i < tmp.size(); ++i)
                {
                    char old = tmp[i];
                    // 每一位字符都从 a 到 z 换一遍
                    for(char ch = 'a'; ch <= 'z'; ++ch)
                    {
                        if(ch != old)
                        {
                            tmp[i] = ch;
                            // bigLevel 中包含 tmp，则说明找到了最短的转化序列
                            if(bigLevel.count(tmp))
                            {
                                return len;
                            }
                            if(dict.count(tmp))
                            {
                                // 将 tmp 从词典中删除，避免往回遍历
                                // 往回遍历就不是最短的转化序列了
                                dict.erase(tmp);
                                nextLevel.insert(tmp);
                            }
                        }
                    }
                    tmp[i] = old; // 恢复成原字符串
                }
            }
            // 看谁会成为数量小的一侧
            if(nextLevel.size() <= bigLevel.size())
            {
                smallLevel.swap(nextLevel);
            }
            else
            {
                bigLevel.swap(nextLevel);
                smallLevel.swap(nextLevel);
            }
            nextLevel.clear();
        }
        return 0;
    }
};


// 普通的广搜
class Solution 
{
private:
    // 由于 wordList 的长度最多是 5000，且只有在词典中
    // 的单词才能入队列，因此 MAXN 设置成 5001
    static const int MAXN = 5001;
    string q[MAXN];

public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        // 将 vector 转成哈希表，用于开始判断某个词是否在词典中
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        // 词典中不包含 endWord，直接返回 0，表示不存在转换序列
        if(!wordSet.count(endWord)) return 0;

        int l = 0, r = 0;
        q[r++] = beginWord;
        unordered_set<string> visited; // 标记哪些字符串已经进过队列了
        visited.insert(beginWord);

        int step = 1;
        while(l < r)
        {
            int n = r - l;
            while(n--)
            {
                string& curStr = q[l++];
                // 找到了路径，返回结果
                if(curStr == endWord) return step;

                // 尝试去替换 curStr 中的每一个字符
                for(int i = 0; i < curStr.size(); ++i)
                {
                    char old = curStr[i];
                    // a ~ z 都尝试去替换掉 old
                    for(char ch = 'a'; ch <= 'z'; ++ch)
                    {
                        if(ch != old)
                        {
                            curStr[i] = ch;
                            if(wordSet.count(curStr) && !visited.count(curStr))
                            {
                                q[r++] = curStr;
                                visited.insert(curStr);
                            }
                        }
                    }
                    curStr[i] = old;
                } 
            }    
            ++step;  
        }

        return 0;
    }
};